#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/16 12:28
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _401_readBinaryWatch.py
from typing import List


class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        nums1 = [8, 4, 2, 1]
        nums2 = [32, 16, 8, 4, 2, 1]

        def dfs(nums:List, count:int, index:int, sum:int, res:List):
            if count==0:
                res.append(sum)
                return
            for i in range(index, len(nums)):
                dfs(nums, count - 1, i + 1, sum + nums[i], res)

        def gen_digits(nums, count) -> List[int]:
            res = []
            dfs(nums, count, 0, 0, res)
            return res

        res = []
        for i in range(turnedOn+1):
            hours = gen_digits(nums1, i)
            minutes = gen_digits(nums2, turnedOn-i)

            for hour in hours:
                if hour>11:continue
                for minute in minutes:
                    if minute > 59:continue
                    minute_str = "0" +str(minute) if minute<10 else str(minute)
                    res.append(str(hour)+":"+minute_str)
        return res

